package ua.mykola.dynamicp;

import static java.lang.Math.max;

public class ZeroOneKnapsack {

	private final Item[] items;
	private final int capacity;
	private final int[][] maxValues;
	private final boolean[][] keep;

	public ZeroOneKnapsack(Item[] items, int capacity) {
		this.items = items;
		this.capacity = capacity;
		maxValues = new int[items.length + 1][capacity + 1];
		keep = new boolean[items.length][capacity + 1];
	}

	public int calcMaxValue() {
		for (int i = 1; i < maxValues.length; i++) {
			for (int c = 1; c <= capacity; c++) {
				if (items[i - 1].weight <= c) {
					int maxValue = max(maxValues[i - 1][c], maxValues[i - 1][c - items[i - 1].weight]
							+ items[i - 1].value);
					maxValues[i][c] = maxValue;
					if (maxValue != maxValues[i - 1][c]) {
						keep[i - 1][c] = true;
					}

				} else {
					maxValues[i][c] = maxValues[i - 1][c];
				}
			}
		}
		return maxValues[items.length][capacity];
	}

	public boolean[] isItemIncluded() {
		boolean[] included = new boolean[items.length];
		int w = capacity;
		for (int i = items.length - 1; i >= 0; i--) {
			if (keep[i][w]) {
				included[i] = true;
				w -= items[i].weight;
			}
		}
		return included;
	}

	public static class Item {
		private int weight;
		private int value;

		public Item(int weight, int value) {
			this.weight = weight;
			this.value = value;
		}
	}
}
